\section{Generátory pseudonáhodných čísel}

Cieľom pseudonáhodných generátorov je vytvárať postupnosti čísel, ktoré sa
navonok javia ako náhodné, hoci v skutočnosti to tak nie je. Dôvodov prečo
by sme chceli niečo takéko je niekoľko, najdôležitejšími sú neprístupnosť
náhodných generátorov a/alebo ich slabá výkonnosť. Ak máme totiž naozaj
náhodný generátor, ktorý ale generuje len 1 bit za sekundu, na
vygenerovanie RSA kľúča by sme potrebovali čakať vyše hodinu.

To, že (pseudo)náhodné čísla potrebujeme v kryptografii je evidentné --
stačí si spomenúť na kryptografické kľúče, príležitostné slová,
inicializačné vektory blokových šifier, náhodné prvky v asymetrických
šifrovacích schémach a schémach na digitálne podpisy, náhodných paddingoch.
Navyše, v mnohých z týchto aplikácii nenáhodnosť ohrozuje bezpečnosť (od
možnosti dešifrovať správu ako pri \todo{} až po úplné prezradenie
súkromného kľúča ako pri \todo{}).

My za preudonáhodný generátor budeme považovať deterministický\footnote{
čo samozrejme priamo znamená, že nenáhodný} algoritmus, ktorý z
počiatočného ``seedu'' vygeneruje dlhú postupnosť. Bez ujmy na strate
všeobecnosti, budeme sa venovať len pseudonáhodným generátorom bitov, čiže
generátorom do postupnosti zloženej z prvkov $\{0,1\}$.

\subsection{Fyzikálne generátory náhodných čísel}
Existuje veľa rôznych spôsobov, ako zkonštruovať generátor náhodných čísel
na základe určitého fyzikálneho javu. Či už ide o jednoduché hádzanie
mince, meranie šumu v polovodičových prvkoch, klopné obvody, ...

Tieto generátory ale môžu byť zaťažené istými chybami -- môžu mať odchýlku
alebo rôzne závislosti medzi jednotlivými vygenerovanými bitmi. Na riešenie
tejto situácie existujú rôzne tzv. ``korektory''. Prirodzene ale musí byť
známe, akou chybou daný generátor trpí.

Uveďme si jednoduchý príklad
\begin{priklad}[Korektor na jednoduchú odchýlku v pravdepodobnosti]
  Uvažujme náhodný generátor bitov, v ktorom sú všetky vygenerované bity
  nezávislé, môže sa ale stať, že bit 0 generujeme s inou pravdepodobnosťou
  ako bit 1.

  Existuje jednoduchý Van Neumannov korektor, ktorý rieši
  daný problém nasledovne: Zakaždým zoberme dvojicu bitov $r_{2i},r_{2i+1}$
  a na výstup dajme nasledovné:
  \begin{itemize}
    \item[00] -- nevypíš nič, opakuj s ďalšou dvojicou bitov
    \item[11] -- nevypíš nič, opakuj s ďalšou dvojicou bitov
    \item[01] -- 0
    \item[10] -- 1
  \end{itemize}
  Pretože bity sú nezávislé, evidentne pravdepodobnosť dvojice 01 a 10 je
  rovnaká. Problémom tejto konštrukcie je ale nejasná priepustnosť --
  môže sa nám stať, že zaradom zahodíme veľa dvojíc. Taktiež, ak je
  vyváženosť narušená dosť výrazne, korekcia je neefektívna pretože
  dominantnou dvojicou bude 00 alebo 11 a budeme teda zahadzovať väčšinu
  vygenerovaných bitov.
\end{priklad}

\subsection{Pseudonáhodné generátory}

\begin{definicia}
    Algoritmus $G$ je pseudonáhodný generátor (PRNG) so vstupom 
    $s \in \{0,1\}^n$ (seed) ak platí:
    \begin{itemize}
        \item existuje polynóm $l(\cdot)$ taký, že
            $|G(s)| = l(n) > n$ (teda generátor generuje dlhšiu postupnosť 
            ako seed, ktorý dostane)
        \item vlastnosť pseudonáhodnosti -- $\forall$ PPT
            algoritmus $D$ platí
            \begin{equation*}
                \Big|Pr[D(r) = 1] - Pr[D(G(s)) = 1]\Big| \leq negl(n)
            \end{equation*}
            kde $r \inr \{0,1\}^{l(n)}, s \inr \{0,1\}^n$ 
            (teda nevieme štatistickým testom rozlíšiť výstupnú postupnosť 
            od náhodnej postupnosti)
    \end{itemize}
\end{definicia}

Táto definícia sa dosť ťažko overuje. Existuje ale takzvaný next-bit test, 
pri ktorom sa ukáže, že ak algoritmus
spĺňa next-bit test, tak je daný algoritmus je PRNG.

\begin{definicia}
    Algoritmus $G$ spĺňa next-bit test, ak pre ľubovoľný PPT
    algoritmus $A$ platí:
    \begin{equation*}
        \forall i < l(n)\colon Pr[A(x_1, x_2, \dots, x_i) = x_{i+1}] \leq \frac{1}{2} + negl(n)
    \end{equation*}
    kde
    $x \in G(s), s \inr \{0,1\}^n$ (teda neexistuje algoritmus, ktorý na základe
    prvých $i$ bitov vie úspešne tipnút nasledujúci bit).
\end{definicia}

\begin{veta}
    Algoritmus $G$ je PRNG práve vtedy ak spĺňa next-bit test.
\end{veta}

\begin{dokaz}
    \noindent
    \begin{itemize}
    \item[$\Rightarrow:$]
        Ak by $G$ nespĺňal Next-bit test,
        tak máme priamo rozlišovací algoritmus.

    \item[$\Leftarrow:$]
        Nech $G$ nespĺňa nejaký štatistický test $A$.
        Na základe neho zostrojíme algoritmus $A'$ pre next-bit test nasledovne:

        Uvažujme distribúcie 
        \begin{align*}
            H_0 &= r_1 r_2 r_3 \dots r_{l(n)} \\
            H_1 &= x_1 r_2 r_3 \dots r_{l(n)} \\
            H_2 &= x_1 x_2 r_3 \dots r_{l(n)} \\
            &\dots \\
            H_{l(n)} &= x_1 x_2 x_3 \dots x_{l(n)}
        \end{align*}
        kde $x_1 \dots x_{l(n)} \leftarrow G(s)$ sú pseudonáhodné bity
        a $r_1 \dots r_{l(n)} \inr \{0,1\}$ sú náhodné bity.

        Keďže $A$ vie rozlišovať medzi $H_0$ a $H_{l(n)}$, tak platí:
        \begin{equation*}
            \Big|Pr[A(t) = 1 | t \in H_0] - 
                 Pr[A(t) = 1 | t \in H_{l(n)}] \Big| 
            \geq \frac{1}{p(n)}
        \end{equation*}
        Bez ujmy na všeobecnosti predpokladajme, 
        že výraz v absolútnej hodnote je kladný.
        Potom ho vieme rozpísať ako:
        \begin{equation*}
        \begin{split}
        &\Big(Pr[A(t) = 1 | t \in H_0] - 
                Pr[A(t) = 1 | t \in H_{1}] \Big) \\ 
        &+\Big(Pr[A(t) = 1 | t \in H_1] - 
                Pr[A(t) = 1 | t \in H_{2}]\Big)\\
        &+ \dots \\
        &+ \Big(Pr[A(t) = 1 | t \in H_{l(n)-1}] - 
                Pr[A(t) = 1 | t \in H_{l(n)}] \Big) \geq \frac{1}{p(n)}
        \end{split}
        \end{equation*}

        A teraz aspoň jeden sčítanec v zátvorke musí byť nezanedbateľný 
        (inak by bol celý výsledok zanedbateľný), čiže 
        $\exists i < l(n)\colon Pr[A(t) = 1 | t \in H_{i}] - 
            Pr[A(t) = 1 | t \in H_{i+1}] \geq \frac{1}{l(n)p(n)}$.

        Next-bit test $A'(x_1 \dots x_i)$ zostrojíme nasledovne:
        Zoberieme postupnosti $s_0 = x_1 \dots x_i 0 r_{i+2} \dots r_{l(n)}$
        a $s_1 = x_1 \dots x_i 1 r_{i+2} \dots r_{l(n)}$.
        Dajme tieto dve postupnosti na vstup rozlišovača $A$.
        Ak bude platiť $A(s_0) = A(s_1)$, tak vratíme $b \inr \{0,1\}$. 
        Ak $A(s_0) = 0 \ne A(s_1)$, tak vrátime 0.
        A napokon, ak $A(s_0) = 1 \ne A(s_1)$, tak vrátime 1.

        Dá sa ukázať, že šanca na úspech bude 
        $\frac{1}{2} + \frac{1}{l(n)p(n)}$.
    \end{itemize}
\end{dokaz}


\noindent
Príkladom pseudonáhodného generátora je generátor podľa štandardu ANSI-X9.17:

Na začiatku nastavíme náhodné hodnoty $K, seed$. 
Vygenerovanie náhodného výstupu vyzerá nasledovne: 
Zoberie sa $timestamp$ a zašifruje sa pomocou kľúča $K$,
čím dostaneme hodnotu $T_i = E_k(timestamp)$. Výstup z generátora bude
hodnota $out = E_k(T_i \oplus seed)$. 
Navyše sa nastaví nový $seed$ ako hodnota $seed=E_k(T_i \oplus out)$.
